//如果有大量重复键值，那么快速排序的时间复杂度几乎要达到平方级别，而归并排序还是不变
//升级版之后，有三个分区，左边是比基准数小的，右边是比基准数大的，中间是和基准数一样的
//dijstra 3-way partition
//用三个指针，两个从左往右遍历，一个从右向左遍历 lt gt i
//lt指向基准数，只要i找到bi基准数小的数，就把i和lt对应位置的数交换，然后二者同时加加
//i如果找到和基准数同样大的数，那么只有i++
//i如果找到比基准数大的数，那么就到gt过来去找比基准数小或者相等的数然后和i交换  只需要gt和i无脑进行交换,然后gt--就行了
//交换完之后再当成上面两种情况进行操作
public class QuickSort_plus extends InsertionSort{
    public void MySort(int data[])
    {
       Shuffle shuffle=new Shuffle();
       shuffle.shuffle(data);
       Sort(data,0,data.length-1);
    }

    public void Sort(int data[],int left,int right)
    {
    //当数组较小的时候采用插入排序
       if(right-left<=5)
       {
        super.MySort_p(data,left,right);
        return ;
       }
       int i=left,gt=right,lt=left,compare=data[left];
       
       while(i<=gt)
       {
        if(data[i]>compare)
        {
          Exchange(data,i,gt);
          gt--;
        }
        else if(data[i]==compare)
        {
          i++;
        }
        else
        {
         Exchange(data,i,lt);
         i++;
         lt++; 
        }
       }
       Sort(data,left,lt-1);
       Sort(data,gt+1,right);
    }
}
